class UnionFind {
	int[] item; // pointers are indexes of these arrays
	int[] weight; // count of items in tree if this is a root.

	UnionFind(int n) {
		item = new int[n];
		weight = new int[n];
		for (int i = 0; i < n; i++) {
			item[i] = -1;
			weight[i] = 1;
		}
	}

	int find(int i) {
		int j = i;
		while (item[j] >= 0)
			j = item[j];
		int root = j;
		while (item[i] >= 0) {
			j = item[i];
			item[i] = root;
			i = j;
		}
		return root;
	}

	void union(int i, int j) {
		i = find(i);
		j = find(j);
		if (i != j) {
			if (weight[i] > weight[j]) {
				weight[i] += weight[j];
				item[j] = i;
			} else {
				weight[j] += weight[i];
				item[i] = j;
			}
		}
	}
}